package com.waiting.leetcode;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/14
 **/
public class BestTimeToBuyAndSellStockWithTransactionFee714 {

    public int maxProfit(int[] p, int fee) {
        if (p.length <= 1) return 0;

        int min = p[0];
        int profit = 0;

        for (int i = 1; i < p.length; i++) {
            min = Math.min(min, p[i - 1] - profit);
            profit = Math.max(profit, p[i] - fee - min);
        }
        return profit;
    }

    public static void main(String[] args) {
        int[] prices = {1, 3, 2, 8, 4, 9};
        int fee = 2;
        System.out.println(maxProfixt3(prices, fee));
    }

    public static int maxProfixt2(int[] prices, int fee) {
        int[] sell = new int[prices.length];
        int[] buy = new int[prices.length];
        buy[0] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            buy[i] = Math.max(buy[i - 1], sell[i - 1] - prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i] - fee);
        }
        return sell[prices.length - 1];
    }

    public static int maxProfixt3(int[] prices, int fee) {
        int buy = -prices[0], sold = 0;
        for (int i = 1; i < prices.length; i++) {
            int tmp = sold;
            sold = Math.max(buy + prices[i] - fee, sold);
            buy = Math.max(buy, tmp - prices[i]);
        }
        return sold;
    }
}
